相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4524
正常题面及题解:http://blog.csdn.net/huanghongxun/article/details/51181809
解题报告
考虑按最大的质因子分类
那么每一次就是用次大的质因子去替换最大的质因子
再用堆来维护一下就好了
Code
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; LL n; int k; int pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127},tot=31; struct Data{ LL w; int k,MX,nxt; inline Data() {} inline Data(LL a, int b, int c, int d):w(a),k(b),MX(c),nxt(d) {} inline bool operator < (const Data &B) const {return w < B.w;} }; priority_queue<Data> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } int main(){ cin>>n>>k; for (int i=1;i<=tot;i++) { LL w = pri[i]; int t = 1; while (w <= n) { que.push(Data(w,t,i,i-1)), w *= pri[i]; t++; } } for (int j=1;j<k;j++) { Data t = que.top(); que.pop(); if (t.k > 1) for (int i=1;i<=t.nxt;i++) { LL tmp = t.w / pri[t.MX] * pri[i]; que.push(Data(tmp,t.k-1,t.MX,i)); } } cout<<que.top().w; return 0; }
But wanna comment that you have a very nice internet site, I enjoy the style and design it actually stands out.
I went over this site and I think you have a lot of good information, saved to my bookmarks (:.